package com.path.algorithms;


import java.util.ArrayList;


public class FindPath {
	private AdjacencyMatrix am;
	private int start, end;
	private ArrayList<Integer> path;
	private ArrayList<Integer> improvedPath;
	private boolean pathFound;
	
	public void find(AdjacencyMatrix am, int start, int end){
		this.am = am;
		this.start = start;
		this.end = end;
		this.path = new ArrayList<Integer>();
		this.improvedPath = new ArrayList<Integer>();
		this.pathFound = false;
		this.moveToVertex(start);
	}

	public boolean moveToVertex(int vertex){
		/*
		 * Depth first search.
		 * 
		 * 
		 * This function seems to work well
		 * but it also has the distinct feeling that it 
		 * is held together by duct-tape
		 * */
		
		int stoppingVertex = vertex;
		this.path.add(vertex);
		if(vertex == this.end || this.pathFound == true){
			this.pathFound = true;
			return true;
		}
		//printPath(this.path);
		ArrayList<Integer> row = this.am.getVertex(vertex);
		boolean loopComplete = false;
		int nextVertex = (vertex + 1) % row.size();
		while(!loopComplete){
			if(nextVertex == stoppingVertex){
				loopComplete = true;
			}
		
			else if(row.get(nextVertex) == 1){
				if(path.contains(nextVertex)){
					//skip this vertex
				}else{
					moveToVertex(nextVertex);
				}
			}
			nextVertex = (nextVertex + 1) % row.size();
		}
		
		if(path.get(path.size() - 1) == this.end){
			return true;
		}
		
		path.remove(path.size() - 1);
		return false;
	}
	
	public ArrayList<Integer> improvePath(){
		/*
		 * Works!
		 * 
		 * Note, this doesn't find the shortest possible
		 * it just finds shortcuts through the given path.
		 * 
		 */
		this.improvedPath.add(this.path.get(0));
		int vertexUnderInvestigation;
		int nextVertexInImprovedPath;
		int count;
		for(int i = 0; i < this.path.size() - 2; i++){
			vertexUnderInvestigation = this.path.get(i);
			nextVertexInImprovedPath = this.path.get(i + 1);
			count = this.path.size() - 1;
			while(count >= i + 2){
				int vertexBeingChecked = this.path.get(count);
				int checkValue = this.am.getAdjacencyMatrix().get(vertexUnderInvestigation).get(vertexBeingChecked);
				if(checkValue == 1){
					nextVertexInImprovedPath = vertexBeingChecked;
					i = this.path.indexOf(nextVertexInImprovedPath) - 1;
					break;
				}
				count--;
			}
			
			this.improvedPath.add(nextVertexInImprovedPath);
			if(nextVertexInImprovedPath == this.path.get(this.path.size() - 1)){
				break;
			}
			
		}
		int improvedPathLastElement = this.improvedPath.get(this.improvedPath.size() - 1);
		int pathLastElement = this.path.get(this.path.size() - 1);
		
		if(improvedPathLastElement != pathLastElement){
			this.improvedPath.add(
					this.path.get(this.path.size() - 1));
		}
		return this.improvedPath;
	}
	
	public ArrayList<Integer> improvePath(ArrayList<Integer> path){
		ArrayList<Integer> temp = this.path;
		this.path = path;
		this.improvePath();
		this.path = temp;
		return this.improvedPath;
	}
	public void printPath(ArrayList<Integer> p){
		for(int i = 0; i < p.size(); i++){
			System.out.print(p.get(i) + ", ");
		}
		System.out.println();
	}

	public ArrayList<Integer> getPath(){
		return this.path;
	}
}
